import collections


class Solution(object):
    def kEmptySlots(self, bulbs, k):
        """
        :type bulbs: List[int]
        :type k: int
        :rtype: int
        """
        left_index = 0
        right_index = 1
        n = len(bulbs)
        new_bulbs = [0] * n
        for i in range(n):
            new_bulbs[bulbs[i] - 1] = i + 1
        bulbs = new_bulbs
        count = 0
        min_time = float('inf')
        min_return = -1
        while right_index < n:
            if count == k:
                if bulbs[right_index] < min_time:
                    if min_return == -1:
                        min_return = max(bulbs[left_index], bulbs[right_index])
                    else:
                        min_return = min(min_return, max(bulbs[left_index], bulbs[right_index]))
                    left_index = right_index
                else:
                    left_index += 1
                    right_index = left_index
                count = 0
                min_time = float('inf')
            else:
                if bulbs[right_index] > bulbs[left_index]:
                    min_time = min(min_time, bulbs[right_index])
                    count += 1
                else:
                    left_index = right_index
                    min_time = float('inf')
                    count = 0
            right_index += 1
        return min_return


data = Solution()
bulbs = [1, 3, 2]
k = 1
print(data.kEmptySlots(bulbs, k))
bulbs = [1, 2, 3]
k = 1
print(data.kEmptySlots(bulbs, k))
bulbs = [6, 5, 8, 9, 7, 1, 10, 2, 3, 4]
k = 2
print(data.kEmptySlots(bulbs, k))
